package leetcode_day._2022._202210._1120;

import general_class.ListNode;

import java.util.HashSet;
import java.util.Set;

/**
 * 817. 链表组件
 * 算法：模拟
 *
 * @author yzh
 * @version 1.0
 * @date 2022/10/12 21:26
 */
public class _12_817 {

    public int numComponents(ListNode head, int[] nums) {
        int ans = 0, pre = 0;
        int[] idx = new int[10010];
        for (int num : nums) idx[num] = 1;
        while (head != null) {
            if (pre == 0 && idx[head.val] == 1) ++ans;
            pre = idx[head.val];
            head = head.next;
        }
        return ans;
    }

    public int numComponentsTwo(ListNode head, int[] nums) {
        int ans = 0;
        Set<Integer> set = new HashSet<>();
        for (int num : nums) set.add(num);
        while (head != null) {
            if (set.contains(head.val)) {
                while (head != null && set.contains(head.val)) head = head.next;
                ++ans;
            } else head = head.next;
        }
        return ans;
    }

}
